# 39/100 二叉树-对称二叉树
# leetcode第101题: https://leetcode.cn/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/10
from typing import Optional
from collections import deque
from leetcode.bds import TreeNode, TreeConverter
import leetcode.bds as bs
import leetcode.test as test


def isSymmetric_level_order(root: Optional[TreeNode]) -> bool:
    """我的方法: 使用层序遍历"""
    queue = deque([root])
    while queue:
        n = len(queue)
        for i in range(n // 2):
            if queue[i] and queue[-i - 1]:
                if queue[i].val != queue[-i - 1].val:
                    return False
            if (not queue[i]) ^ (not queue[-i - 1]):  # 异或运算符 表示"只有一个不为空"或者"只有一个为空"
                return False
        for i in range(n):
            cur = queue.popleft()
            if cur:
                queue.append(cur.right)
                queue.append(cur.left)
    return True


def isSymmetric_sync(root: Optional[TreeNode]) -> bool:
    """使用同步移动的方式遍历左右两个子树来判断是否对称, 使用递归来遍历两个子树"""

    def check(p: Optional[TreeNode], q: Optional[TreeNode]):
        if not p and not q:  # p和q都为空
            return True
        if not p or not q:  # p和q有一个为空
            return False
        return p.val == q.val and check(p.left, q.right) and check(p.right, q.left)

    return check(root.left, root.right)


if __name__ == '__main__':
    t1 = TreeConverter.list_to_tree([1, 2, 2, 3, 4, 4, 3])
    t2 = TreeConverter.list_to_tree([2, 1, 3])
    t3 = TreeConverter.list_to_tree([1, 2, 2, None, 3, None, 3])
    t4 = TreeNode(1)
    inp = [{"root": t1}, {"root": t2}, {"root": t3}, {"root": t4}, ]
    out = [True, False, False, True]
    test.test_function(isSymmetric_level_order, inp, out)
    test.test_function(isSymmetric_sync, inp, out)
